import java.util.*;
public class HeapSort {
	public static int left(int i)
	{
		return 2*i;
	}
	
	public static int right(int i)
	{
		return 2*i + 1;
	}
	
	public static void exchange(int[] A, int i, int j)
	{
		int temp=0;
		temp = A[i];
		A[i] = A[j];
		A[j] = temp;
	}
	
	public static void maxHeapify(int[] A, int i, int heapSize)
	{
		int l = left(i);
		int r = right(i);
		int largest = 0;
		if(l <= heapSize && A[l] > A[i])
			largest = l;
		else
			largest = i;
		if(r <= heapSize && A[r] > A[largest])
			largest = r;
		
		if (largest != i)
		{
			exchange(A, i, largest);
			maxHeapify(A, largest, heapSize);
		}
	}
	
	public static void buildMaxHeap(int[] A)
	{
		int i = (A.length-1)/2;
		for(;i>0;i--)
		{
			maxHeapify(A,i, A.length-1);
		}
	}
	
	public static void heapSort(int[] A)
	{
		int heapSize = 0;
		heapSize = A.length - 1;
		buildMaxHeap(A);
		for(;heapSize >= 2; )
		{
			exchange(A, 1, heapSize);
			maxHeapify(A, 1, --heapSize);
		}
		
		
	}
	
	public static void main(String[] args)
	{
		int[] A = {0,4,1,3,2,16,9,10,14,8,7};
		heapSort(A);
		System.out.println(Arrays.toString(A));
		
	}

}
